package Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * \* Created with IntelliJ IDEA.
 * \* User: Administrator
 * \* Date: 2022/5/7
 * \* Time: 11:55
 * \* To change this template use File | Settings | File Templates.
 * \* Description:
 * \
 */
public class Demo3 {
    public static void main(String[] args) {
        String str = "aaba";
        int count = minCut(str);
    }
    public static boolean[][] getMat(String s){
        int len = s.length();
        boolean[][] Mat = new boolean[len][len];
        for(int i = len - 1; i >= 0; --i){
            for(int j = i; j < len; ++j){
                if(j == i)
    // 单字符为回文字符串
                    Mat[i][j] = true;
                else if(j == i + 1){
    // 相邻字符如果相同，则为回文字符串
                    if(s.charAt(i) == s.charAt(j))
                        Mat[i][j] = true;
                    else
                        Mat[i][j] = false;
                } else{
    // F(i,j) = {s[i]==s[j] && F(i+1,j-1)
    // j > i+1
                    Mat[i][j] = (s.charAt(i) == s.charAt(j)) && Mat[i + 1][j - 1];
                }
            }
        }
        return Mat;
    }


    public static int minCut(String s) {
        int len = s.length();
        if(len == 0)
            return 0;
        boolean[][] Mat = getMat(s);
        int[] minCut = new int[len + 1];
    // F(i)初始化
    // F(0）= -1，必要项，如果没有这一项，对于重叠字符串“aaaaa”会产生错误的结果
        for(int i = 0; i <= len; ++i){
            minCut[i] = i - 1;
        }
        for(int i = 1; i <= len; ++i){
            for(int j = 0; j < i; ++j){
    // F(i) = min{F(i), 1 + F(j)}, where j<i && j+1到i是回文串
    // 从最长串判断，如果从第j+1到i为回文字符串
    // 则再加一次分割，从1到j，j+1到i的字符就全部分成了回文字符串
                if(Mat[j][i - 1]){
                    minCut[i] = Math.min(minCut[i], minCut[j] + 1);
                }
            }
        }
        return minCut[len];
    }



    public static void main4(String[] args) {
        String str1 = "ADOBECODEBANC";
        String str2 = "ABC";
        String str = minWindow(str1,str2);
    }

    public static String minWindow(String s, String t) {
        int[] map = new int[128];
        for(char ch : t.toCharArray()){
            map[ch]++;
        }
        //字符t的数量
        int count = t.length();
        int left = 0;
        int right = 0;
        int windowLen = Integer.MAX_VALUE;
        int start = 0;
        while (right < s.length()){
            if(map[s.charAt(right++)]-- > 0){
                count--;
            }
            while (count == 0){
                if (right - left < windowLen){
                    windowLen = right-left;
                    start = left;
                }
                if(map[s.charAt(left++)]++ == 0){
                    count++;
                }
            }
        }
        if(windowLen != Integer.MAX_VALUE){
            return s.substring(start,start+windowLen);
        }
        return "";
    }
//    输入：s = "ADOBECODEBANC", t = "ABC"
//    输出："BANC"
    public static String minWindow1(String s, String t) {
        int[] map = new int[128];
        //记录字符串t中每个字符的数量
        for (char ch : t.toCharArray())
            map[ch]++;
        //字符串t的数量
        int count = t.length();
        int left = 0;//窗口的左边界
        int right = 0;//窗口的右边界
        //覆盖t的最小长度
        int windowLength = Integer.MAX_VALUE;
        //覆盖字符串t开始的位置
        int strStart = 0;
        while (right < s.length()) {
            if (map[s.charAt(right++)]-- > 0){
                count--;
            }

            //如果全部覆盖
            while (count == 0) {
                //如果有更小的窗口就记录更小的窗口
                if (right - left < windowLength) {
                    windowLength = right - left;
                    strStart = left;
                }
                if (map[s.charAt(left++)]++ == 0)
                    count++;
            }
        }
        //如果找到合适的窗口就截取，否则就返回空
        if (windowLength != Integer.MAX_VALUE)
            return s.substring(strStart, strStart + windowLength);
        return "";
    }



    private static int totalFruit(int[] arr) {
        if(arr == null|| arr.length == 0) return 0;
        int n = arr.length;
        Map<Integer,Integer> map = new HashMap<>();
        int maxLen = 0;
        int left = 0;

        for(int right = 0;right<n;right++){
            map.put(arr[right],map.getOrDefault(arr[right],0)+1);
            while (map.size() > 2){
                map.put(arr[left],map.get(arr[left]) - 1);
                if(map.get(arr[left]) == 0){
                    map.remove(arr[left]);
                }
                left++;
            }
            maxLen = Math.max(maxLen,right-left +1);
        }
        return maxLen;
    }

    public static int totalFruit1(int[] fruits) {
        int n = fruits.length;
        if(n <=2 ) return  n;
        int ans = 0;
        int left = 0;
        int right = 0;
        int[] freq = new int[n];
        int count = 0;
        while(right < n){
            freq[fruits[right]]++;
            if(freq[fruits[right]] == 1) count++;
            right++;
            while(count > 2){
                freq[fruits[left]]--;
                if(freq[fruits[left]] == 0) count--;
                left++;
            }
            ans = Math.max(ans,right-left);
        }
        return ans;
    }

    public static void main3(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String str = scanner.nextLine();
            StringBuilder sb = new StringBuilder();
            for(int i=0 ;i< str.length();i++){
                char c = str.charAt(i);
                if(c == ' '){
                    sb.append(" ");
                    continue;
                }
                int n = c - 'A';
                if(n >= 5){
                    char tmp =(char)(c-5);
                    sb.append(tmp);
                }else {
                    char tmp = (char) ('Z' - 4 + n);
                    sb.append(tmp);
                }
            }
            System.out.println(sb.toString());
        }
    }

    public static void main2(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int num = scanner.nextInt();
            int count = 0;//因子个数
            for (int i = 2; i < Math.sqrt(num); i++) {
                if(num % i == 0){
                    while (num % i == 0){
                        num = num / i;
                    }
                    count++;
                }
            }
            if(num != 1){//最终的num如果是素数结果肯定不为1,因子个数也需要++;
                count++;
            }
            System.out.println(count);
        }
    }

    public static void main1(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String str = sc.nextLine();
            StringBuilder sb = new StringBuilder();
            for(int i =0;i<str.length();i++){
                char c = str.charAt(i);
                if(c == ' '){
                    sb.append(" ");
                    continue;
                }
                int n = c - 'A';
                if(n >= 5){
                    char tmp = (char) (c-5);
                    sb.append(tmp);
                }else {
                    char tmp = (char) ('Z' - 4 + n);
                    sb.append(tmp);
                }
            }
            System.out.println(sb.toString());
        }

    }
}
